#pragma once
#include "string"

class ReusableIndirectHeap {

public:
	static float* keyList;
	static int* inList;
	static int* outList;
	int heapSize;

	static float defaultKey;

	static int* ticketCheck;
	static int ticketCheckSize;
	static int ticketNumber;

	class Context {
		public:
			float* keyList;
			int* inList;
			int* outList;
			int* ticketCheck;
			int ticketNumber;
			Context(){};
	};

	static void loadContext(Context context) {
		ReusableIndirectHeap::keyList = context.keyList;
		ReusableIndirectHeap::inList = context.inList;
		ReusableIndirectHeap::outList = context.outList;
		ReusableIndirectHeap::ticketCheck = context.ticketCheck;
		ReusableIndirectHeap::ticketNumber = context.ticketNumber;
	}

	static void saveContext(Context context) {
		context.keyList = ReusableIndirectHeap::keyList;
		context.inList = ReusableIndirectHeap::inList;
		context.outList = ReusableIndirectHeap::outList;
		context.ticketCheck = ReusableIndirectHeap::ticketCheck;
		context.ticketNumber = ReusableIndirectHeap::ticketNumber;
	}

	static void initialise(int size, float defaultKey) {
		ReusableIndirectHeap::defaultKey = defaultKey;

		if (ticketCheck == nullptr || ticketCheckSize != size) {
			//System.out.println("REINITIALISE HEAP " + size);
			if (ticketCheck==nullptr)
			{
				delete []ticketCheck;
			}
			keyList = new float[size];
			inList = new int[size];
			outList = new int[size];
			ticketCheck = new int[size];
			ticketNumber = 1;
			ticketCheckSize = size;
		}
		else if (ticketNumber == -1) {
			ticketCheck = new int[size];
			ticketNumber = 1;
		}
		else {
			ticketNumber++;
		}
	}

	static float getKey(int index) {
		return ticketCheck[index] == ticketNumber ? keyList[index] : defaultKey;
	}

	static int getIn(int index) {
		return ticketCheck[index] == ticketNumber ? inList[index] : index;
	}

	static int getOut(int index) {
		return ticketCheck[index] == ticketNumber ? outList[index] : index;
	}

	static void setKey(int index, float value) {
		if (ticketCheck[index] != ticketNumber) {
			keyList[index] = value;
			inList[index] = index;
			outList[index] = index;
			ticketCheck[index] = ticketNumber;
		}
		else {
			keyList[index] = value;
		}
	}

	static void setIn(int index, int value) {
		if (ticketCheck[index] != ticketNumber) {
			keyList[index] = defaultKey;
			inList[index] = value;
			outList[index] = index;
			ticketCheck[index] = ticketNumber;
		}
		else {
			inList[index] = value;
		}
	}

	static void setOut(int index, int value) {
		if (ticketCheck[index] != ticketNumber) {
			keyList[index] = defaultKey;
			inList[index] = index;
			outList[index] = value;
			ticketCheck[index] = ticketNumber;
		}
		else {
			outList[index] = value;
		}
	}

	ReusableIndirectHeap()
	{
		initialise(0, FLT_MAX);
		heapSize = 0;
	}
	/**
	* Runtime: O(1)
	*/
	 ReusableIndirectHeap(int size) {
		//initialise(size, Float.POSITIVE_INFINITY);
		initialise(size, FLT_MAX);
		heapSize = 0;
	}

	/**
	* Runtime: O(1)
	*/
	ReusableIndirectHeap(int size, int memorySize) {
		//initialise(memorySize, Float.POSITIVE_INFINITY);
		initialise(memorySize, FLT_MAX);

		heapSize = 0;
	}

	/**
	* Runtime: O(n)
	*/
	/*public void heapify() {
	for (int i=heapSize/2-1; i>=0; i--) {
	bubbleDown(i);
	}
	}*/


	void bubbleUp(int index) {
		int parent = (index - 1) / 2;
		while (index > 0 && getKey(index) < getKey(parent)) {
			// If meets the conditions to bubble up,
			swapData(index, parent);
			index = parent;
			parent = (index - 1) / 2;
		}
	}

	void swapData(int a, int b) {
		// s = Data at a = out[a]
		// t = Data at b = out[b]
		// key[a] <-> key[b]
		// in[s] <-> in[t]
		// out[a] <-> out[b]

		int s = getOut(a);
		int t = getOut(b);

		swapKey(a, b);
		swapIn(s, t);
		swapOut(a, b);
	}

	/**
	* swap integers in list
	*/
	void swapKey(int i1, int i2) {
		float temp = getKey(i1);
		setKey(i1, getKey(i2));
		setKey(i2, temp);
	}

	/**
	* swap integers in list
	*/
	void swapOut(int i1, int i2) {
		int temp = getOut(i1);
		setOut(i1, getOut(i2));
		setOut(i2, temp);
	}

	/**
	* swap integers in list
	*/
	void swapIn(int i1, int i2) {
		int temp = getIn(i1);
		setIn(i1, getIn(i2));
		setIn(i2, temp);
	}

	int smallerNode(int index1, int index2) {
		if (index1 >= heapSize) {
			if (index2 >= heapSize)
				return -1;

			return index2;
		}
		if (index2 >= heapSize)
			return index1;

		return getKey(index1) < getKey(index2) ? index1 : index2;
	}

	void bubbleDown(int index) {
		int leftChild = 2 * index + 1;
		int rightChild = 2 * index + 2;
		int smallerChild = smallerNode(leftChild, rightChild);

		while (smallerChild != -1 && getKey(index) > getKey(smallerChild)) {
			// If meets the conditions to bubble down,
			swapData(index, smallerChild);

			// Recurse
			index = smallerChild;
			leftChild = 2 * index + 1;
			rightChild = 2 * index + 2;
			smallerChild = smallerNode(leftChild, rightChild);
		}
	}

	/**
	* Runtime: O(lgn)
	*/
	void decreaseKey(int outIndex, float newKey) {
		// Assume newKey < old key
		int inIndex = getIn(outIndex);

		// Optimisation: Jump the newly set value to the bottom of the heap.
		// Faster if there are a lot of POSITIVE_INFINITY values.
		// This is equivalent to an insert operation.
		if (getKey(inIndex) ==FLT_MAX/* Float.POSITIVE_INFINITY*/) {
			swapData(inIndex, heapSize);
			inIndex = heapSize;
			++heapSize;
		}
		setKey(inIndex, newKey);

		bubbleUp(inIndex);
	}

	float getMinValue() {
		return getKey(0);
	}

	/**
	* Runtime: O(lgn)
	* @return index of min element
	*/
	int popMinIndex() {
 		if (heapSize == 0)
			return -1;
			//throw new NullPointerException("Indirect Heap is empty!");
		else if (heapSize == 1) {
			--heapSize;
			return getOut(0);
		}
		// nodeList.size() > 1

		// s = Data at 0 = out[0]
		// t = Data at lastIndex = out[lastIndex]
		// key[0] = key[lastIndex], remove key[lastIndex]
		// in[s] = -1
		// in[t] = 0
		// out[0] = out[lastIndex], remove out[lastIndex]

		//E temp = keyList.get(0);
		int s = getOut(0);
		swapData(0, heapSize - 1);

		--heapSize;
		bubbleDown(0);

		return s;
	}


	std::string arrayToString() {
		std::string sb = std::to_string(getIn(1)) + " / ";
		for (int i = 0; i<ticketCheckSize; i++) {
			if (i == heapSize) sb.append("* ");
			sb.append("[");
			sb.append(std::to_string(getOut(i)));
			sb.append(" ");
			float val = getKey(i);
			sb.append(val == FLT_MAX/* Float.POSITIVE_INFINITY*/ ? "_" : std::to_string((int)val));
			sb.append("], ");
		}
		return sb;
	}

	/*
	private static final int parent(int index) {
	return (index-1)/2;
	}

	private static final int leftChild(int index) {
	return 2*index+1;
	}

	private static final int rightChild(int index) {
	return 2*index+2;
	}
	*/

	int size() {
		return heapSize;
	}

	bool isEmpty() {
		return heapSize <= 0;
	}

	static void clearMemory() {
		if (keyList)
		{
			delete[]keyList;
		}
		if (inList)
		{
			delete[]inList;
		}
		if (outList)
		{
			delete[]outList;
		}
		if (ticketCheck)
		{
			delete[]ticketCheck;
		}
		keyList = nullptr;
		inList = nullptr;
		outList = nullptr;
		ticketCheck = nullptr;
		ticketCheckSize = 0;
	}
};